# -*- coding: utf-8 -*-

"""
@Time    : 2020/2/20 16:54
@Author  : Chen Liu
@FileName: numof_island.py
@Software: PyCharm

"""


# 岛屿数量，求连通块的个数
# 解法一：并查集
# class Solution:
#     def find(self, x, fa):
#         if fa[x] == x:
#             return x
#         fa[x] = self.find(fa[x], fa)
#         return fa[x]
#
#     def numIslands(self, grid):
#             n = len(grid)
#             if n == 0:
#                 return 0
#
#             m = len(grid[0])
#
#             fa = [0] * (n*m)
#             for i in range(n):
#                 for j in range(m):
#                     fa[i * m + j] = i * m + j
#             print("fa: ", fa)
#
#             for i in range(n):
#                 for j in range(m):
#                     if grid[i][j] == '1':
#                         # print(fa)
#                         # 把在同一集合的所有的点变为第一次遇见的点对应的索引
#                         if i > 0 and grid[i-1][j] == '1':
#                             a = self.find((i-1)*m + j, fa)
#                             print((i-1)*m + j)
#                             print("a: ", a)
#                             b = self.find(i * m + j, fa)
#                             print(i*m+j)
#                             print("b: ", b)
#                             fa[b] = a
#                             # print("fa: ", fa)
#
#                         if j > 0 and grid[i][j-1] == '1':
#                             a = self.find(i*m + j-1, fa)
#                             b = self.find(i*m + j, fa)
#                             fa[b] = a
#
#             print("modify: ", fa)
#             res = 0
#             for i in range(n):
#                 for j in range(m):
#                     if grid[i][j] == '1':
#                         a = self.find(i*m + j, fa)
#                         print("a: ", a)
#                         if a == i*m + j:
#                             res += 1
#
#             return res


# 解法二：深度优先遍历
class Solution:
    def dfs(self, grid, i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i, j - 1)
        self.dfs(grid, i, j + 1)

    def numIslands(self, grid) -> int:
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    count += 1
                    self.dfs(grid, i, j)

        return count


if __name__ == "__main__":
    grid = [['1', '1', '0', '0', '0'], ['1', '1', '0', '0', '0'], ['0', '0', '1', '0', '0'], ['0', '0', '0', '1', '1']]
    s = Solution()
    res = s.numIslands(grid)
    print("res: ", res)
